/**
 * Created with Intellij JDEA
 * Description:
 * User:
 * Date:2022-05-28
 * Time:17:59
 */
public class 把数组排成最小的数 {
    class Solution {
        public String minNumber(int[] nums) {
            int n = nums.length;

            String[] str = new String[n];
            for(int i = 0;i < nums.length;i++) {
                str[i] = String.valueOf(nums[i]);
            }
            sort(str,0,n-1);
            StringBuffer sb = new StringBuffer();
            for(String s : str) {
                sb.append(s);
            }
            return sb.toString();
        }

        public void sort(String[] str,int left,int right) {
            if(left >= right){
                return;
            }
            int i = left,j = right;
            String tmp = str[i];
            while(i<j) {
                while(i<j && (str[j]+str[left]).compareTo(str[left]+str[j]) >= 0) {
                    j--;
                }
                while(i<j && (str[i]+str[left]).compareTo(str[left]+str[i]) <= 0) {
                    i++;
                }
                tmp = str[i];
                str[i] = str[j];
                str[j] = tmp;
            }
            str[i] = str[left];
            str[left] = tmp;
            sort(str,left,i-1);
            sort(str,i+1,right);
        }
    }
}
